package q_2_2;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import junit.framework.Assert;

import org.junit.Test;

public class Q_2_2 {

	public static class Node {
		public Integer value;
		public Node next;
	}
	
	public static Integer findNthLast(Node head, int n) {
		if(n < 0){return null;}
		Node first = head;
		while(n >= 0){
			if(first == null) {return null;}
			first = first.next; n--;
		}
		Node second = head;
		while(first != null) {
			first = first.next;
			second = second.next;
		}
		return second.value;
	}
	
	public static Node getNode (List<Integer> list) {
		Node head = null;
		Node tail = null;
		for(Integer i : list) {
			Node cur = new Node();
			cur.value = i;
			if (tail == null) {
				head = cur;
				tail = head;
			} else {
				tail.next = cur;
				tail = tail.next;
			}
		}
		return head;
	}
	
	@Test
	public void test() {
		Assert.assertEquals(null, findNthLast(getNode(new LinkedList<Integer>()), -1));
		Assert.assertEquals(null, findNthLast(getNode(new LinkedList<Integer>()), 0));
		Assert.assertEquals(Integer.valueOf(1), findNthLast(getNode(Arrays.asList(1)), 0));
		Assert.assertEquals(null, findNthLast(getNode(Arrays.asList(1)), 1));
		Assert.assertEquals(null, findNthLast(getNode(Arrays.asList(1)), -1));
		Assert.assertEquals(Integer.valueOf(2), findNthLast(getNode(Arrays.asList(1, 2)), 0));
		Assert.assertEquals(Integer.valueOf(1), findNthLast(getNode(Arrays.asList(1, 2)), 1));
	}

}
